package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * binary
 * 1574. 删除最短的子数组使剩余数组有序
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/16 21:54
 */
public class FindLengthOfShortestSubarray {

    public static void main(String[] args) {
        FindLengthOfShortestSubarray test = new FindLengthOfShortestSubarray();

        // 3
//        int[] arr = {1,2,3,10,4,2,3,5};

        // 4
        int[] arr = {5, 4, 3, 2, 1};

        // 0
//        int[] arr = {1,2,3};

        int lengthOfShortestSubarray = test.findLengthOfShortestSubarray(arr);
        System.out.println(lengthOfShortestSubarray);
    }

    public int findLengthOfShortestSubarray(int[] arr) {
        int length = arr.length;
        int a = -1;
        for (int i = 1; i < length; i++) {
            if (arr[i] < arr[i - 1]) {
                a = i - 1;
                break;
            }
        }
        if (a == -1) {
            return 0;
        }
        int b = 0;
        for (int i = length - 1; i >= 0; i--) {
            if (arr[i - 1] > arr[i]) {
                b = i;
                break;
            }
        }
        int max = Math.max(a + 1, length - b);
        for (int i = a; i >= 0; i--) {
            int v = find(arr, b, length - 1, arr[i]);
            max = Math.max(max, i + length - v);
        }
        return length - max;
    }

    private int find(int[] arr, int st, int end, int t) {
        if (t <= arr[st]) {
            return st - 1;
        }
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (arr[m] < t) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }

}
